// The implementation for Single linkage and complete linkage.
package roman.algorithm;

import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;

public class SingleClustering {
	
	 int [][] sim;
	 int problemSize;
	 int leastClusters = 5;
	 int multiplier = 2000000000;		// the biggest value can be represented by an int is 2147483647.  
	 HashSet<Integer> nodeSet = new HashSet<Integer>();
	 List<Node> nodeList = new ArrayList<Node>();
	 TreeMap<Integer,Edge> map = new TreeMap<Integer,Edge>();
	 
	 HashMap<Integer,LinkedList<Integer>> results = new HashMap<Integer,LinkedList<Integer>>();
	 Map<Integer, String> nameTable = new HashMap<Integer,String>();
	 Set<String> baseSet = new HashSet<String>();
	
	 class Node{
		int setName;
		Node parent;					// nodes with parent null is the name of the set
		public Node(int n, Node p){
			setName = n;
			parent = p;
		}
	}
	
	 class Edge{
		int fromNode;
		int toNode;
		public Edge(int a, int b){
			fromNode = a;
			toNode = b;
		}
		public boolean equals(Object e){
			Edge o = (Edge) e;
			if(fromNode==o.fromNode && toNode == o.toNode)
				return true;
			if(fromNode==o.toNode && toNode == o.fromNode)
				return true;
			return false;
		}
	}
	
	public int find(int i){
		if(nodeList.get(i).parent == null)
			return i;
		else{
			int tmp = find(nodeList.get(i).parent.setName);
			nodeList.get(i).parent = nodeList.get(tmp);
			return tmp;
		}
	}
	
	public void updateSim(int a, int b){
		// the similarity metric implemented here is complete linkage
		// b is the bigger value
		for(int i = 0; i < problemSize; i++)
			if(sim[a][i] != 0)
				map.remove(sim[a][i]);
		
		for(int i = 0; i < problemSize; i++)
			if(sim[b][i] != 0)
				map.remove(sim[b][i]);
		
		for(int i = 0; i < problemSize; i++)
			if(nodeSet.contains(i) && i != b)
				//sim[b][i] = Math.min(sim[b][i], sim[a][i]);
				sim[b][i] = Math.max(sim[b][i], sim[a][i]);
		
		for(int i =0; i < b; i++)
			if(nodeSet.contains(i)){
				sim[i][b]=sim[b][i];
				insertNode(b,i);
			}
		
		for(int i = b+1; i<problemSize; i++){
			if(nodeSet.contains(i)){
				sim[i][b] = sim[b][i];
				insertNode(i,b);
			}
		}
	}
	
	public void insertNode(int i, int j){
		if(sim[i][j] != 0){
			while(map.containsKey(sim[i][j])){
				sim[i][j] = sim[i][j]+1;
				sim[j][i] = sim[i][j];
			}
			map.put(sim[i][j], new Edge(i,j));
		}
	}
	
	public void join(){
		if(map.size()==0)
			return;
		Edge tmpEdge = map.get(map.lastKey());
		int fromNode, toNode;
		fromNode = tmpEdge.fromNode;
		toNode = tmpEdge.toNode;
		nodeSet.remove(toNode);
		updateSim(toNode,fromNode);
		nodeList.get(toNode).parent = nodeList.get(fromNode);
	}
	
	public void process() throws Exception{
		problemSize = 25;
		readFile("dataAm25.in","artists25.in","artists25.in");
		
		for(int i=0; i<problemSize; i++){
			nodeList.add(new Node(i,null));
			nodeSet.add(i);
		}
		
		for(int i = 0; i < problemSize; i++)
			for(int j = 0; j < i; j++)
				insertNode(i, j);
		
		for(int i = 0; i<(problemSize - leastClusters); i++)
			join();
		
		int tmp;
		for(int i = 0; i<problemSize; i++){
			tmp = find(i);
			if(results.containsKey(tmp))
				results.get(tmp).add(i);
			else{
				results.put(tmp, new LinkedList<Integer>());
				results.get(tmp).add(i);
			}
		}
		
		Collection<LinkedList<Integer>> value = results.values();
		Iterator<LinkedList<Integer>> itv = value.iterator();
		String name;
		while(itv.hasNext()){
			Iterator<Integer> it = itv.next().iterator();
			while(it.hasNext()){
				name = nameTable.get(it.next());
				if(baseSet.contains(name)){
					System.out.print(name+"\t");
				}
			}
			System.out.println();
			System.out.println();
		}
	}
	
	public void readFile(String f1, String f2, String f3) throws Exception{
		sim = new int[problemSize][problemSize];
		
		Scanner sc = new Scanner(new FileInputStream(f1));
		int i = 0, j = 0;
		while(sc.hasNext()){
			double tmpD =sc.nextDouble();
			sim[i][j] = (int)(tmpD*multiplier);
			j++;
			if(j == problemSize){
				j = 0;
				i++;
			}
		}
		
		String line;
		sc = new Scanner(new FileInputStream(f2));
		while(sc.hasNextLine()){
			line = sc.nextLine();
			String[] tmp = line.split(",");
			nameTable.put(Integer.parseInt(tmp[0]), tmp[1]);
		}
		
		sc = new Scanner(new FileInputStream(f3));
		while(sc.hasNextLine()){
			line = sc.nextLine();
			String[] tmp = line.split(",");
			baseSet.add(tmp[1]);
		}
	}
	
	public static void main(String[] argv) throws Exception{
		SingleClustering o = new SingleClustering();
		o.process();
	}
}
